/*
基数排序（Radix Sort）是一种非比较排序算法，它将整数按位数切割成不同的数字，然后将每个位数分别比较排序。
基数排序的时间复杂度为 $O(d(n+k))$，其中 $d$ 表示整数位数，$k$ 表示每个位数可能的取值范围。

基数排序的实现可以采用桶排序的思想来完成，具体操作如下：
1. 创建一个 10 个桶的数组  bucketList ，一个存放未排序数字的临时数组  numberList ，以及一个  maxDigit  表示最大数字的位数；
2. 从最低位开始，依次按照当前位数上的数字把未排序数字放到对应的桶中；
3. 把各个桶中的数字按照顺序依次取出来，放回  numberList  数组与矩阵；
4. 重复第 2 步和第 3 步，直到所有位数都按照从低到高的顺序排完为止。
 */
function radixSort(arr) {
    const bucketList = Array.from({ length: 10 }, () => []);
    const numberList = [...arr];
    let maxDigit = getMaxDigit(arr);
    for (let i = 0; i < maxDigit; i++) {
        for (let j = 0; j < numberList.length; j++) {
            const digit = getDigit(numberList[j], i);
            bucketList[digit].push(numberList[j]);
        }
        numberList.length = 0;
        for (let j = 0; j < bucketList.length; j++) {
            numberList.push(...bucketList[j]);
            bucketList[j] = [];
        }
    }
    return numberList;
}
function getMaxDigit(arr) {
    let max = 0;
    for (let i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i].toString().length);
    }
    return max;
}
function getDigit(num, i) {
    return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}
